// 课程表2

package Leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

class Solution_210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // <课程，入度值>
        Map<Integer, Integer> indegree = new HashMap<>();
        // <课程，指向的课程>
        Map<Integer, List<Integer>> relation = new HashMap<>();
        // 最终的拓扑序列
        List<Integer> result = new ArrayList<>();
        // 初始化哈希表
        for (int i = 0; i < numCourses; i++) {
            indegree.put(i, 0);
        }
        for (int[] array : prerequisites) {
            indegree.put(array[1], indegree.get(array[1]) + 1);

            if (!relation.containsKey(array[0]))
                relation.put(array[0], new ArrayList<>());
            relation.get(array[0]).add(array[1]);
        }

        // 初始化队列，将入度为0的点放入队列
        Deque<Integer> deque = new LinkedList<>();
        for (Map.Entry<Integer, Integer> entrySet : indegree.entrySet()) {
            if (entrySet.getValue() == 0)
                deque.addLast(entrySet.getKey());
        }

        // 队列逐渐出队，表示学习该门课程
        while (!deque.isEmpty()) {
            // 队头节点
            int index = deque.removeFirst();
            result.add(index);
            if (relation.containsKey(index) == false)
                continue;
            // 该节点指向的节点
            List<Integer> list = relation.get(index);
            // 调整入度，如果为0则入队
            for (int i : list) {
                indegree.put(i, indegree.get(i) - 1);
                if (indegree.get(i) == 0)
                    deque.addLast(i);
            }
        }

        // 此时遍历indegree如果入度有不为0则表示存在环
        for (Map.Entry<Integer, Integer> entrySet : indegree.entrySet()) {
            if (entrySet.getValue() != 0)
                return new int[0];
        }
        Collections.reverse(result);
        return result.stream().mapToInt(Integer::valueOf).toArray();
    }
}